import Graph from "./Graph";
import {Colors, initializeColor} from "./initializeColor";
import Dictionary from "../map/Dictionary";

export function depthFirstSearch<T>(graph: Graph<T>, callback?: Function) {
    const vertices = graph.getVertices();
    const adjacencyList = graph.getAdjacencyList()
    const color = initializeColor<T>(vertices);

    for (let i = 0; i < vertices.length; i++) {
        if (color.get(vertices[i]) === Colors.WHITE) {
            depthFirstSearchVisit(vertices[i], color, adjacencyList, callback)
        }
    }

}

function depthFirstSearchVisit<T>(node: T, color: Map<T, Colors>, adjList: Dictionary<T, T[]>, callback?: Function) {
    color.set(node, Colors.GREY);
    if (callback) {
        callback(node);
    }
    const neighbors = adjList.get(node)?.value || [];
    for (let i = 0; i < neighbors?.length; i++) {
        const w = neighbors[i];
        if (color.get(w) === Colors.WHITE) {
            depthFirstSearchVisit(w, color, adjList, callback);
        }
    }
    color.set(node, Colors.BLACK)
}

namespace depthFirstSearchPlus {
    export function depthFirstSearch<T>(graph: Graph<T>, callback?: Function) {
        const vertices = graph.getVertices();
        const adjacencyList = graph.getAdjacencyList()
        const color = initializeColor<T>(vertices);
        const discovery = new Map<T, number>(); // 发现时间
        const finished = new Map<T, number>(); // 完全探索时间
        const predecessors = new Map<T, T | null>(); // 父节点
        const time = {count: 0}
        for (let i = 0; i < vertices.length; i++) {
            discovery.set(vertices[i], 0);
            finished.set(vertices[i], 0);
            predecessors.set(vertices[i], null);
        }

        for (let i = 0; i < vertices.length; i++) {
            if (color.get(vertices[i]) === Colors.WHITE) {
                depthFirstSearchVisit(vertices[i], color, adjacencyList, callback,discovery,finished,predecessors,time)
            }
        }

    }

    function depthFirstSearchVisit<T>(node: T, color: Map<T, Colors>, adjList: Dictionary<T, T[]>, callback?: Function , discovery: Map<T, number>, finished: Map<T, number>,predecessors: Map<T, T | null>,time: {count: number}) {
        color.set(node, Colors.GREY);
        if (callback) {
            callback(node);
        }
        time.count++;

        discovery.set(node,time.count)
        finished
        const neighbors = adjList.get(node)?.value || [];

        for (let i = 0; i < neighbors?.length; i++) {
            const w = neighbors[i];
            if (color.get(w) === Colors.WHITE) {
                predecessors.set(w,node);
                depthFirstSearchVisit(w, color, adjList, callback,discovery,finished,predecessors,time);
            }
        }
        color.set(node, Colors.BLACK)
    }
}


const graph = new Graph<string>();
const myVertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]
for (let i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}

graph.addEdge(myVertices[0], myVertices[1])
graph.addEdge(myVertices[0], myVertices[2])
graph.addEdge(myVertices[0], myVertices[3])
graph.addEdge(myVertices[2], myVertices[6])
graph.addEdge(myVertices[3], myVertices[5])
graph.addEdge(myVertices[6], myVertices[1])

console.log(graph.toString())


depthFirstSearch(graph, (n: any) => console.log(n))



